//反转字符串中的单词

class Solution {
public:
    string reverseWords(string s) 
    {
        //去除多余的空格 保证单词之间只有一个空格
        removeExtraSpace(s);
        reverse(s.begin(),s.end());
        int curi=0;
        for(int i=0;i<=s.size();i++)
        {
            if(i==s.size() || s[i]==' ')
            {
                reverse(s.begin()+curi,s.begin()+i);
                curi=i+1;
            }
        }
        return s;
    }
    void removeExtraSpace(string& s)
    {
        int cur=0;//这个相当于 当前要更新的下标
        for(int i=0;i<s.size();i++)
        {
            if(s[i]!=' ')
            {
                //如果不是第一个单词 那么单词和单词之间需要加空格
                if(cur!=0) 
                {
                    s[cur++]=' ';
                }
                while(s[i]!=' ' && i<s.size())
                {
                    s[cur++]=s[i++];
                }
                // s[cur++]=' ';
            }
        }
        s.resize(cur);
    }
};
//替换空格

class Solution {
public:
    string replaceSpace(string s) 
    {
        //看看有几个空格 有一个空格就要扩容两个
        int size=0;
        int oldsize=s.size()-1;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]==' ') size++;
        }
        s.resize(s.size()+size*2);
        int j=s.size()-1;
        while(j>=0 && oldsize>=0)
        {
            if(s[oldsize]!=' ')
            {
                s[j--]=s[oldsize--];
            }
            else
            {
                s[j--]='0';
                s[j--]='2';
                s[j--]='%';
                oldsize--;
            }

        }
        return s;
    }
};

//四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        //如果target>0 且 nums[0]>target 直接返回空向量
        //如果target <0   nums[0]>target 可以直接返回空向量吗？ -4 > -10 但依然有可能和达到-10
        //所以去重条件 要看target 也要看 nums[0]大于0还是小于0
        vector<vector<int>>res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++)
        {
            //第一个数就不符合 直接返回Res即可
            if(nums[0]>target && nums[i]>0) return res;
            if(i>0 && nums[i]==nums[i-1]) continue;

            for(int j=i+1;j<nums.size();j++)
            {
                //中间如果不符合条件 应该跳出循环 而不能直接返回res
                if(nums[i]+nums[j] >target &&  nums[i]+nums[j]>=0) break;
                if(j>i+1 && nums[j]==nums[j-1]) continue;
                int l=j+1;int r=nums.size()-1;
                while(l<r)
                {
                    long sum=(long)nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum > target) r--;
                    else if(sum <target) l++;
                    else 
                    {
                        res.push_back(vector<int>{nums[i],nums[j],nums[l],nums[r]});
                        while(l<r && nums[l]==nums[l+1]) l++;
                        while(l<r && nums[r]==nums[r-1]) r--;
                        l++;
                        r--;
                    }
                }
            }
        }
        return res;
    }
};

//赎金信

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) 
    {
        int hash[26]={0};
        for(int i=0;i<magazine.size();i++)
        {
            hash[magazine[i]-'a']++;
        }
        for(int i=0;i<ransomNote.size();i++)
        {
            if(hash[ransomNote[i]-'a']==0) return false;
            hash[ransomNote[i]-'a']--;
        }
        return true;
    }
};